﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


class MergeSortArray
{

    public static int[] MergeSort(int[] a)
    {
        if (a.Length == 1)
        {
            return a;
        }
        int middle = a.Length / 2;
        int[] left = new int[middle];
        for (int i = 0; i < middle; i++)
        {
            left[i] = a[i];
        }
        int[] right = new int[a.Length - middle];
        for (int i = 0; i < a.Length - middle; i++)
        {
            right[i] = a[i + middle];
        }
        left = MergeSort(left);
        right = MergeSort(right);

        int leftptr = 0;
        int rightptr = 0;

        int[] sorted = new int[a.Length];
        for (int i = 0; i < a.Length; i++)
        {
            if (leftptr < left.Length && rightptr < right.Length)
            {
                if (left[leftptr] < right[rightptr])
                {
                    sorted[i] = left[leftptr++];
                }
                else
                {
                    sorted[i] = right[rightptr++];
                }
            }
            else
            {
                if (leftptr < left.Length)
                {
                    sorted[i] = left[leftptr++];
                }
                else
                {
                    sorted[i] = right[rightptr++];
                }
            }
        }
        return sorted;
    }
    
    static void Main()
    {
        int[] numbers = {6, 5, 3, 1, 8, 7, 2, 4};       
        MergeSort(numbers);
        foreach (var x in MergeSort(numbers))
        {
            Console.WriteLine(x);
        }

    }
}

